package cn.cxq.learning.sort;

import java.util.Arrays;

/**
 * 快速排序：对冒泡排序的优化
 */
public class QuickSort {

    //取中间值作为基准数
    public static int[] printSort(int[] arr, int left, int right){

        int leftBound = left;
        int rightBound = right;

        int middle = arr[(left + right)/2];

        while (leftBound < rightBound) {
            while (arr[leftBound] < middle) leftBound++;
            while (arr[rightBound] > middle) rightBound--;

            if (leftBound >= rightBound) break;

            int temp = arr[leftBound];
            arr[leftBound] = arr[rightBound];
            arr[rightBound] = temp;

            while (leftBound <arr.length && arr[leftBound] == middle) leftBound ++;
            while (rightBound > 0 && arr[rightBound] == middle) rightBound --;

//            if (arr[leftBound] == middle) rightBound --;
//            if (arr[rightBound] == middle) leftBound ++;

            System.out.println(Arrays.toString(arr));
        }



        if (leftBound == rightBound) {
            leftBound ++;
            rightBound --;
        }

        if (left < rightBound) printSort(arr, left, rightBound);
        if (leftBound < right) printSort(arr, leftBound, right);
        return arr;
    }

    public static int[] sort(int[] arr, int left, int right){

        int leftBound = left;
        int rightBound = right;

        int middle = arr[(left + right)/2];

        while (leftBound < rightBound) {
            while (arr[leftBound] < middle) leftBound++;
            while (arr[rightBound] > middle) rightBound--;

            if (leftBound >= rightBound) break;

            int temp = arr[leftBound];
            arr[leftBound] = arr[rightBound];
            arr[rightBound] = temp;

            if (arr[leftBound] == middle) rightBound --;
            if (arr[rightBound] == middle) leftBound ++;
        }

        if (leftBound == rightBound) {
            leftBound ++;
            rightBound --;
        }

        while (arr[leftBound] == middle && leftBound <arr.length) leftBound ++;
        while (arr[rightBound] == middle && rightBound > 0) rightBound --;

//        if (left < rightBound) sort(arr, left, rightBound);
//        if (leftBound < right) sort(arr, leftBound, right);
        return arr;
    }

    public static int[] sort2(int[] arr, int left, int right){

        if (left >= right){
            return arr;
        }

        int leftBound = left;
        int rightBound = right;
        int temp = arr[left];

        while (leftBound < rightBound){

            while (leftBound < rightBound && arr[rightBound] >= temp) rightBound --;

            if (leftBound < rightBound) arr[leftBound ++] = arr[rightBound];

            while (leftBound < rightBound && arr[leftBound] < temp) leftBound ++;

            if (leftBound < rightBound) arr[rightBound --] = arr[leftBound];

        }

        arr[leftBound] = temp;

        sort2(arr, left, leftBound - 1);
        sort2(arr, leftBound + 1, right);

        return arr;
    }

    public static int[] printSort2(int[] arr, int left, int right){

        if (left >= right){
            return arr;
        }

        int leftBound = left;
        int rightBound = right;
        int key = arr[left];



        while (leftBound < rightBound){

            while (leftBound < rightBound && arr[rightBound] >= key) rightBound --;

            if (leftBound < rightBound) arr[leftBound ++] = arr[rightBound];

            while (leftBound < rightBound && arr[leftBound] < key) leftBound ++;

            if (leftBound < rightBound) arr[rightBound --] = arr[leftBound];
        }

        arr[leftBound] = key;

        System.out.println(Arrays.toString(arr));

        printSort2(arr, left, leftBound - 1);
        printSort2(arr, leftBound + 1, right);

        return arr;
    }
}
